package LeetcodeTest_forty_two;
//LCP 22. 黑白方格画
public class paintingPlan
{
    public static void main(String[] args)
    {
        System.out.println(solution.paintingPlan(4,13));
    }
}
class solution
{
    public static int paintingPlan(int n, int k)
    {
        int i,j,answer;
        answer=0;
        if(k==0)
            return 1;
        else if(k<n)
            return 0;
        else if(k==n*n)
            return 1;
        else
        {
            for(i=0;i<n;i++)
            {
                double x=(k-i*n)/((n-i)*1.0);
                if(x!=(int)x)
                {
                    continue;
                }
                else
                {
                    j=(int)x;
                    answer+=fun(n,i)*fun(n,j);
                }
            }
            return answer;
        }
    }
    //求组合数
    public static int fun(int n,int x)
    {
        int g,k,h;
        g=k=1;
        h=x;
        if(x==0)
            return 1;
        if(x<0)
            return 0;
        while (h>=1)
        {
            g*=n;
            n--;
            h--;
        }
        while (x>0)
        {
            k*=x;
            x--;
        }
        return g/k;
    }
}